package Tree;

import java.util.ArrayList;
import java.util.List;

public class SonTree<T> {

    private int treeSize;//���Ĵ�С
    private int nodeSize;//�ڵ���
    private Node<T>[] elementData;//��������ֵ

    @SuppressWarnings("unchecked")
    public SonTree(T data) {
        treeSize = 20;
        nodeSize = 0;
        elementData = new Node[100];
        elementData[0] = new Node<T>(data, null, 0);
        nodeSize++;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        SonTree<String> sonTree = new SonTree<String>("000");
        Node<String> root = sonTree.elementData[0];
        sonTree.add("101", root, 1);
        sonTree.add("102", root, 1);
        sonTree.add("201", sonTree.getNode("101"), 2);
        System.out.println(sonTree);
        System.out.println(sonTree.getChildNode(sonTree.getNode("101")));
    }

    public void add(T data, Node<T> parent, int deep) {
        if (nodeSize + 1 > treeSize) {
            throw new IndexOutOfBoundsException("�������Ĵ�С");
        }
        int newDeep = 0;
        for (int i = 0; i < nodeSize; i++) {
            if (elementData[i].equals(parent)) {
                newDeep = parent.deep;
                break;
            }
        }
        if (deep != newDeep + 1) {
            throw new IndexOutOfBoundsException("������ȴ���");
        }
        //�����ӽڵ㲹λ�գ��ø��ڵ��ָ��ָ���ӽڵ㣬����Ϊ���ڵ��ָ��
        if (parent.sonNode != null) {
            parent = parent.sonNode;
        }


        for (int i = 0; i < treeSize; i++) {
            if (elementData[i] == null) {
                elementData[i] = new Node<T>(data, null, deep);
                parent.sonNode = elementData[i];
                nodeSize++;
                return;
            }
        }

    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int i = 0; i < nodeSize; i++) {
            sb.append(elementData[i].data + ",");
        }
        sb.append("]");
        sb.delete(sb.length() - 2, sb.length() - 1);
        return sb.toString();
    }

    //����ӽڵ�
    public List<Node<T>> getChildNode(Node<T> rootNode) {
        List<Node<T>> list = new ArrayList<Node<T>>();
        int deep = rootNode.deep + 1;
        for (int i = 0; i < nodeSize; i++) {
            if (elementData[i].equals(rootNode.sonNode) && deep == rootNode.sonNode.deep) {
                rootNode = rootNode.sonNode;//�õ��ӽڵ������
                list.add(elementData[i]);
            }
        }
        return list;
    }

    //����ֵ��ýڵ�
    public Node<T> getNode(T data) {
        for (int i = 0; i < nodeSize; i++) {
            if (elementData[i].data.equals(data)) {
                return elementData[i];
            }
        }
        return null;
    }

    public static class Node<E> {
        private E data;
        private Node<E> sonNode;
        private int deep;

        public Node(E data, Node<E> sonNode, int deep) {
            super();
            this.data = data;
            this.sonNode = sonNode;
            this.deep = deep;
        }

        @Override
        public String toString() {
            return "����:" + data;
        }

    }

}
